// https://www.lintcode.com/problem/permutation-index/

public class Solution {
    /**
     * @param A: An array of integers
     * @return: A long integer
     */
    public long permutationIndex(int[] A) {
        // write your code here
        // [1, 2, 3]如果排成[3, ?, ?]说明1和2的排列都已经用掉了。那么序号至少从4开始。所以根据逆序求阶乘就可以。
        // [4, 1, 3, 2]展开：ret从1开始计数
        // 4, rc = 0, fact = 1
        // [1, 3, 2]
        // 4 > 1 rc = 1, fact = 1
        // 4 > 3 rc = 2, fact = 2
        // 4 > 2 rc = 3, fact = 6
        // ret += 3 * 6 = 19
        // 1, rc = 0, fact = 1
        // [3, 2]
        // 1 < 3 rc = 0
        // 1 < 2 rc = 0
        // 3, rc = 0, fact = 1
        // [2]
        // 3 > 2 rc = 1, fact = 1
        // ret += 1 * 1 = 20
        long ret = 1;
        for (int i = 0; i < A.length; ++i) {
            long fact = 1;
            long rc = 0;
            for (int j = i + 1; j < A.length; ++j) { // 从当前元素看后面有几个逆序
                if (A[i] > A[j]) {
                    ++rc;
                }
                fact *= (j - i);
            }
            ret += rc * fact;
        }
        return ret;
    }
}